package Offer025;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 链表中两数相加
 *
 * @author 23737
 * @time 2021.12.11
 */
public class Test {
    public static void main(String[] args) {
        ListNode listNode = new ListNode(7);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(4);
        ListNode listNode4 = new ListNode(3);
        listNode.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;

        ListNode listNode5 = new ListNode(5);
        ListNode listNode6 = new ListNode(6);
        ListNode listNode7 = new ListNode(4);
        listNode5.next = listNode6;
        listNode6.next = listNode7;
        ListNode listNode1 = new Solution().addTwoNumbers(listNode, listNode5);
        while (listNode1 != null) {
            System.out.print(listNode1.val + " ");
            listNode1 = listNode1.next;
        }
    }
}


class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

/**
 * 栈
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Deque<Integer> stack1 = new LinkedList<>();
        Deque<Integer> stack2 = new LinkedList<>();
        while (l1 != null) {
            stack1.push(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            stack2.push(l2.val);
            l2 = l2.next;
        }
        ListNode newHead = new ListNode(-1);
        int add = 0;
        while (!stack1.isEmpty() || !stack2.isEmpty() || add != 0) {
            int sum = add;
            sum += stack1.isEmpty() ? 0 : stack1.poll();
            sum += stack2.isEmpty() ? 0 : stack2.poll();
            add = sum / 10;
            ListNode cur = new ListNode(sum % 10);
            cur.next=newHead.next;
            newHead.next = cur;
        }
        return newHead.next;
    }
}